// 给定一个数组nums，要求计算出数组中的逆序对的总数
// 逆序对：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对

// 思路：归并排序，分为分解过程和合并过程，合并过程是两个有序数组的合并，在合并的时候计算逆序对

let cnt = 0
function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let mid = Math.floor((arr.length / 2))
    let leftArr = mergeSort(arr.slice(0, mid))
    let rightArr = mergeSort(arr.slice(mid))
    return merge(leftArr, rightArr)
}

function merge(leftArr, rightArr) {
    let res = []
    let index1 = 0
    let index2 = 0
    while (index1 < leftArr.length && index2 < rightArr.length) {
        // 这里必须是小于等于，这样不是逆序对
        if (leftArr[index1] <= rightArr[index2]) {
            res.push(leftArr[index1])
            index1++
        } else {
            cnt += leftArr.length - index1 //这是是统计逆序对的个数，这个差值正好都符号逆序对
            res.push(rightArr[index2])
            index2++
        }
    }
    if (index1 < leftArr.length) {
        result = res.concat(leftArr.slice(index1))
    }
    if (index2 < rightArr.length) {
        result = res.concat(rightArr.slice(index2))
    }
    return result
}

let arr = [7, 5, 6, 4];
mergeSort(arr)
console.log(cnt)